package it.crosato.stage.server.model.phylogeny;

import java.util.Vector;

public class UPGMA {

	int K;			// Numero di cluster
	ClusterUPGMA[] cluster;		//  I cluster dell'albero risultante

	/**
	 * Costruisce l'albero a partire dalla lista degli organismi e dalla
	 * matrice di distanza
	 * @param ds matrice di distanza
	 * @param org lista degli organismi
	 */
	public UPGMA(double[][] ds, Vector<String> org) {
		int N = ds.length;
		cluster = new ClusterUPGMA[2*N-1];
		for (int i=0; i<N; i++)
			cluster[i] = new ClusterUPGMA(i, ds[i], org.get(i));
		K = N;
		while (K < 2*N-1)
			findAndJoin();
	}

	/**
	 * Ritorna la radice dell'albero
	 * @return il cluster radice
	 */
	public ClusterUPGMA getRoot()
	{
		return cluster[K-1];
	}

	/**
	 * Ritorna la distanza tra due cluster
	 * @param i indice primo cluster
	 * @param j indice secondo cluster
	 * @return distanza tra i cluster
	 */
	public double d(int i, int j)
	{
		return cluster[Math.max(i, j)].dmat[Math.min(i, j)];
	}

	/**
	 * Cerca la coppia di cluster da unire e li unisce
	 */
	void findAndJoin() {
		int mini = -1, minj = -1;
		double mind = Double.POSITIVE_INFINITY;
		for (int i=0; i<K; i++)
			if (cluster[i].live())
				for (int j=0; j<i; j++)
					if (cluster[j].live()) {
						double d = d(i, j);
						if (d < mind) {
							mind = d;
							mini = i;
							minj = j;
						}
					}
		join(mini, minj);
	}

	/**
	 * Unisce la coppia di cluster in uno unico rimuovendo ed elimina i due cluster
	 * @param i indice primo cluster
	 * @param j indice secondo cluster
	 */
	public void join(int i, int j) {
		double[] dmat = new double[K];
		for (int m=0; m<K; m++)
			if (cluster[m].live() && m != i && m != j)
				dmat[m] = (d(i, m) * cluster[i].card + d(j, m) * cluster[j].card)
				/ (cluster[i].card + cluster[j].card);
		cluster[K] = new ClusterUPGMA(K, cluster[i], cluster[j], d(i, j) / 2, dmat);
		cluster[i].kill();
		cluster[j].kill();
		K++;
	}
}
